import java.awt.Graphics;
import java.util.*;
import javax.swing.JPanel;
import java.awt.event.KeyEvent;

public class Solver {
	
	//private static final int SLEEPTIME = 50;
	private int speed = 50;
	private Board b_init, b_display;
	//private boolean done = false;
    private JPanel parent;
    private int moves;
    final static int DUMB = 0, SMART = 1;
    final static int SIZE = Board.SIZE;
    private Stack tries;
    private boolean interrupted;
    public static int UNWIND=0, NEWTRY=1, SOLVED=2, INVALID=3;
    public SudokuApplet app;
    private int hlX, hlY;
    private SolverThread st;

	public Solver(JPanel p, Board b, SudokuApplet a)
	{
		parent = p;
		app = a;
		tries = new Stack();
		setBoard(b);
		moves = 0;
		removeHighlight();
		st = null;
	}
	
	public void setBoard(Board b)
	{
		if (st != null) {
			st.terminate();
		}
	    st = null;
		b_init = b_display = b;
		b.setSolver(this);
		while (!tries.isEmpty())
			tries.pop();
		tries.push(new SolverStep(b));
	}
	
	public Board getInitBoard()
	{
		return b_init;
	}
	
	public void paint(Graphics g, int width, int height)
	{
		b_display.paint(g, width, height, hlX, hlY);
	}
	
	public void setDisplay(Board d)
	{
	    b_display = d;
	}
	
	public void addMove()
	{
		moves++;
		//System.out.print(++moves + " ");
		//if (moves % 20 == 0)
		//System.out.println();
	}
 
    public void repaint()
    {
        parent.repaint();
    }
  
    public void showBoardAndWait(Board d)
    {
        setDisplay(d);
        int sleeptime = speed;
        if (speed < 1) sleeptime = 1;
        if (speed > 0 || moves % 1000 == 0) {
        	repaint();
        	app.updateStatus("Solving ("+moves+" moves)");
        	try { Thread.sleep(sleeptime); } catch (InterruptedException e) {}
    	}
    }

    public void showBoardAndWait()
    {
    	showBoardAndWait(((SolverStep) tries.peek()).getBoard());
    }

    public boolean isStarted () {
    	return (st != null && st.isStarted());
    }

    public void solve()
    {
        solve(SMART);
    }
 
    public void solve(int how)
    {
    	// validate initial board state
		b_init.updateAllCells();
		
		int status = NEWTRY;
		if (!b_init.isValid())
			System.out.println("Can't solve");
		else {
	    	while (status != SOLVED && status != INVALID && !interrupted) {
		        //if (how == DUMB)
		        //    dumbIterate();
		        status = smartIterate();
		        if (status != UNWIND)
		        	addMove();
		        showBoardAndWait();
	    	}
		}
		if (interrupted) {
			//app.updateStatus("Interrupted after "+moves+" moves");
		} else if (status == SOLVED)
			app.updateStatus("Solved in "+moves+" moves");
		else
			app.updateStatus("Invalidated in "+moves+" moves");
		repaint();
	}
	
	public void setSpeed (int s)
	{
		speed = s;
	}
	
	public void highlightClickedCell (int x, int y, int width, int height)
	{
		int[] vals = b_init.getCellAt(x,y,width,height);
		hlX = vals[0];
		hlY = vals[1];
		repaint();
	}
	
	public void removeHighlight () //int x, int y, int width, int height)
	{
		hlX = -1;
		hlY = -1;
	}
	
	public void reset()
	{
		// stop the thread if necessary
		interrupted = true;
		if (st != null) {
			st.terminate();
		}
		
		SolverStep lastStep = null;
		//unwind the stack
		while (!tries.isEmpty())
			lastStep = (SolverStep)tries.pop();
		
		if (lastStep != null) {
			Board b = lastStep.getBoard();
			b_display = b;
	        tries = new Stack();
			tries.push(new SolverStep(b));
		}
		
		moves = 0;
		app.updateStatus("Updated puzzle");
	}
	
	public void updateBoardDef ()
	{
		app.setBoardDef(b_init.toString());
	}
	
	public void moveHighlight(KeyEvent e)
	{
		int x = 0;
		int y = 0;
		int code = e.getKeyCode();
		if (code == KeyEvent.VK_DELETE || code == KeyEvent.VK_BACK_SPACE) {
			updateHighlightedCell(' ');
			return;
		}
		if (code == KeyEvent.VK_UP) {
			y = -1;
		} else if (code == KeyEvent.VK_DOWN) {
			y = 1;
		} else if (code == KeyEvent.VK_LEFT) {
			x = -1;
		} else if (code == KeyEvent.VK_RIGHT) {
			x = 1;
		}
		int newX = hlX+x;
		int newY = hlY+y;
		if ((newX != hlX || newY != hlY) &&
				newX >= 0 && newX < SIZE &&
				newY >= 0 && newY < SIZE
		) {
			hlX = newX;
			hlY = newY;
			repaint();
		}
	}
	
	public void updateHighlightedCell(char c)
	{
		if (hlX >= 0 && hlY >= 0) {
			if (c >= '0' && c <= '9') {
	        	reset();
				int newnum = c-'0';
				b_init.setPermanentCellValue(hlX, hlY, newnum);
			} else if (c == ' ' || c == '.') {
	        	reset();
				b_init.clearPermanentCellValue(hlX, hlY);
			}
			updateBoardDef();
			repaint();
		}
	}
	
	/*
	    public void dumbIterate()
	    {
	        boolean solved = true;
	        for (int y = 0; y < SIZE; y ++) {
	            for (int x = 0; x < SIZE; x ++) {
	                if (getCellValue(x, y) <= 0) {
	                    solved = false;
	                    // find a number to try
	                    for (int i = 1; i <= SIZE; i ++) {
	                        if (possibleCellValue(x, y, i)) {
	                            Board tryboard = new Board(this);
	                            tryboard.setCellValue(x, y, i);
	                            solver.showBoardAndWait(tryboard);
	                            Board resultboard = tryboard.dumbSolver();
	                            if (resultboard == null) {
	                                solver.showBoardAndWait(this);
	                            } else {
	//                                System.out.println("Got solved recursively!");
	                                return resultboard;
	                            }
	                        }
	                    }
	                    // no valid numbers found! keep trying
	                    return null;
	                }
	            }
	        }
	        if (solved) {
	            System.out.println("Solved!");
	            solver.showBoardAndWait(this);
	            return this;
	        }
	        System.out.println("Not solved!");
	        solver.showBoardAndWait(this);
	        return null;
	    }
	    */
	
	public int smartIterate()
	{
		SolverStep lastStep = (SolverStep)tries.peek();
		SolverStep nextStep = lastStep.iterate();
		if (nextStep == null) {
			// no solutions found in step; unwind
			SolverStep last = (SolverStep)tries.pop();
			if (tries.isEmpty()) {
				tries.push(last);
				return INVALID;
			}
			return UNWIND;
		} else if (nextStep != lastStep) {
			tries.push(nextStep);
			return NEWTRY;
		} else if (lastStep.isSolved()) {
			return SOLVED;
		}
		return INVALID;
	}
	
	public void interrupt()
	{
		interrupted = true;
		app.updateStatus("Interrupted after "+moves+" moves");
	}
	
	public void start() 
	{
		if (st != null) {
			st.terminate();
			st = null;
		}
		st = new SolverThread();
		interrupted = false;
		st.start();
	}
	
	private class SolverThread extends Thread {
		private boolean started;
		
		public SolverThread() {
			super();
			started = false;
		}
	
		public void terminate () {
	        started = false;
		}
		
	    public boolean isStarted () {
	    	return started;
	    }
	    
	    public void run() {
	    	started = true;
	        solve();
	    }
	}
}
